package q946_validateStackSequences;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    /*
    直接模拟一个栈 看是否能够复现进出的过程即可
    例如 当发现当前栈顶元素与popped[idx]相同 就循环弹出
    最后检查栈中是否还有元素
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int idx = 0;
        for (int i = 0; i < pushed.length; ++i) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[idx]) {
                stack.pop();
                idx++;
            }
        }
        return stack.isEmpty();
    }
}
